package leetcode75;

import base.ListNode;
import base.TreeNode;

import java.util.*;

public class LeetCode {

    public static int getIntValue() {
        int kk = 1;
        kk++;
        return kk;
    }

    public static void printArray() {
        List<Integer> array = Arrays.asList(1,2,3);
        System.out.println("printArray:"+ array.toString());
    }

    public static void printMap() {
        Map<String, String> map = new HashMap<>();
        map.put("singer", "五月天");
        map.put("song", "伤心的人别听慢歌");
        System.out.println("printMap:"+ map);
    }

    public static void printList() {
        List<String> list = new ArrayList<>();
        list.add("123");
        list.add("456");
        list.add("789");
        list.add("123");
        list.set(1, "456456");
        int qq = 1758922263;
//        list.remove("123");
//        List<String> newList = list.subList(0,2);
//        newList.add("888");
        List<String> newList2 = new ArrayList<>();
        newList2.add("123");
        newList2.add("888");
        try {
            list.addAll(1, newList2);
        } catch (Exception e) {

        }

//        boolean retainAll = list.retainAll(newList2);
        System.out.println("printList:"+ list);
        System.out.println("printList2Array:"+ Arrays.toString(list.toArray()));
//        System.out.println("printNewList:"+ newList);
//        System.out.println("printNewList2 retainAll:"+ retainAll+", list:" + list);
    }

    public static void testIterator() {
        List<String> list = new ArrayList<>();
        list.add("123");
        list.add("456");
        list.add("789");
        Iterator iterator = list.iterator();
        do {
            System.out.println("printListNext:"+ iterator.next());
            iterator.remove();
        } while (iterator.hasNext());
        System.out.println("printList:"+ list);
//        while(iterator.hasNext()) {
//            iterator.remove();
//            System.out.println("printListNext:"+ iterator.next());
//        }
    }

    public static void testLinkedList() {
        LinkedList<String> list = new LinkedList<>();
        list.add("123");
        list.add("456");
        list.add("789");
    }

    //拥有最多糖果的孩子
    public static List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int maxCandy = 0;
        List<Boolean> resList = new ArrayList<>();
        for (int i = 0; i < candies.length; i++) {
            int candy = candies[i];
            if (candy > maxCandy) {
                maxCandy = candy;
            }
        }
        for (int i = 0; i < candies.length; i++) {
            int candy = candies[i];
            resList.add(maxCandy - candy <= extraCandies);
        }

//        Iterator it = candyList.iterator();
//        System.out.println("candyList:"+ candyList.toString());
//        while(it.hasNext()) {
//            int num = (Integer) it.next();
//            if (num > maxCandy) {
//                maxCandy = num;
//            }
//        }
//        while(it.hasNext()) {
//            int num = (Integer) it.next();
//            resList.add(maxCandy - num >= 0);
//        }
        return resList;
    }

    //种花问题
    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
//        List<Integer> list = new ArrayList<>();
//        int addFlowerNum = 0;
//        for (int i = 0; i < flowerbed.length; i++) {
//            list.add(flowerbed[i]);
//        }
//        int size = list.size();
//        if (size == 1 && list.get(0) == 0) {
//            return true;
//        }
//        if (list.size() >= 2 && (list.get(0) == 0 && list.get(1) == 0)) {
//            list.set(0,1);
//            addFlowerNum++;
//        }
//        if (list.size() >= 2 && (list.get(size-2) == 0 && list.get(size-1) == 0)) {
//            list.set(size-1,1);
//            addFlowerNum++;
//        }
//
//        for (int i = 1; i < list.size() - 1; i++) {
//            int fFlower = list.get(i-1);
//            int aFlower = list.get(i+1);
//            int cFlower = list.get(i);
//            if (fFlower == 0 && aFlower == 0 &&  cFlower == 0) {
//                addFlowerNum++;
//                list.set(i, 1);
//            }
//        }
//
//        return addFlowerNum >= n;

        for (int i = 0, len = flowerbed.length; i < len && n > 0;) {
            if (flowerbed[i] == 1) {
                i += 2;
            } else if (i == flowerbed.length - 1 || flowerbed[i + 1] == 0) {
                n--;
                i += 2;
            } else {
                i += 3;
            }
        }
        return n <= 0;
    }

    //冒泡排序
    public static int[] bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i +1; j < nums.length; j++) {
                int temp = nums[i];
                if (nums[i] < nums[j]) {
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        return nums;
    }

    public static int[] quickSort(int[] nums, int left, int right) {
        if (left > right) {
            return new int[] {};
        }
        int baseNum = nums[left];
        int i = left;
        int j = right;
        while (i != j) {
            while(nums[j] >= baseNum && i < j) {
                j--;
            }
            while(nums[i]<=baseNum && i<j) {
                i++;
            }
            //i、j未相遇时，在它们停下的位置进行交换
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        //i、j未相遇时，交换基准元素与i，j相遇位置元素
        nums[left] = nums[i];
        nums[i] = baseNum;

        quickSort(nums, left, i-1);
        quickSort(nums, i+1, right);
        return nums;
    }

    //删除链表倒数第n个节点-双指针法
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int i = 0;
        ListNode beforeNode = new ListNode();
        beforeNode.next = head;
        ListNode leftNode = beforeNode;
        ListNode rightNode = beforeNode;
        boolean moveLeft = false;
        while (rightNode.next != null) {
            rightNode = rightNode.next;
            if (i == n) {
                moveLeft = true;
            }
            if (moveLeft) {
                leftNode = leftNode.next;
            }
            i++;
        }
        if (leftNode.next != null) {
            leftNode.next = leftNode.next.next;
        }
        return beforeNode.next;
    }

    //反转链表
    public static ListNode reverseList(ListNode head) {
        ListNode prevNode = null;
        ListNode curNode = head;
        while (curNode.next != null) {
            ListNode tempNode = curNode.next;
            curNode.next = prevNode;
            prevNode = curNode;
            curNode = tempNode;
        }
        return prevNode;
    }


    //删除链表中间元素
    public static ListNode deleteMiddle(ListNode head) {
        if (head == null) return null;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next;
            fast = fast.next;
        }
        if (slow.next != null) {
            slow.next = slow.next.next;
        }
        return head;
    }

    //二叉树遍历-前序遍历-递归
    public static List<Integer> inorderTraversalBefore(TreeNode root) {
        List<Integer> nodes = new LinkedList<>();
        dfsBefore(root, nodes);
        return nodes;
    }

    public static void dfsBefore(TreeNode root, List<Integer> nodes) {
        if (root != null) {
            nodes.add(root.val);
            dfsBefore(root.left, nodes);
            dfsBefore(root.right, nodes);
        }
    }

    //二叉树遍历-前序遍历-基于栈实现
    public static List<Integer> inorderTraversalBeforeByStack(TreeNode root) {
        List<Integer> nodes = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;
        while (curNode != null || !stack.isEmpty()) {
            while (curNode != null) {
                nodes.add(curNode.val);
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.pop();
            curNode = curNode.right;
        }
        return nodes;
    }

    //二叉树遍历-中序遍历-递归
    public static List<Integer> inorderTraversalMid(TreeNode root) {
        List<Integer> nodes = new LinkedList<>();
        dfsMid(root, nodes);
        return nodes;
    }

    public static void dfsMid(TreeNode root, List<Integer> nodes) {
        if (root != null) {
            dfsMid(root.left, nodes);
            nodes.add(root.val);
            dfsMid(root.right, nodes);
        }
    }

    //二叉树遍历-中序遍历-基于栈实现
    public static List<Integer> inorderTraversalMidByStack(TreeNode root) {
        List<Integer> nodes = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;
        while (curNode != null || !stack.isEmpty()) {
            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.pop();
            nodes.add(curNode.val);
            //遍历一个节点后，再遍历他的右子树
            curNode = curNode.right;
        }
        return nodes;
    }



    public static int maxArraySum(int[] array) {
        if (array.length <= 1) {
            return array.length > 0 ? array[0] : 0;
        }
        int maxSum = array[0];
//        for (int i = 0; i < array.length; i++) {
//            int sum = 0;
//            for (int j = i; j < array.length; j++) {
//                sum += array[j];
//                if (sum > maxSum) {
//                    maxSum = sum;
//                }
//            }
//        }
        int left = 0;
        int right = 1;
        while (left < array.length) {
            int sum = array[left];
            int numr = array[right];
            if (sum + numr > sum) {
                sum += numr;
                right++;
            } else {

            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        System.out.println("getIntValue:"+ getIntValue());
        printArray();
        printMap();
        printList();
        testIterator();
        System.out.println("kidsWithCandies:"+ kidsWithCandies(new int[] {2,3,5,1,3}, 3));
        System.out.println("canPlaceFlowers:"+ canPlaceFlowers(new int[] {1,0,0,0,1}, 1));
    }
}
